package likou;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/08/21 12:24
 */
public class _188 {
    public static void main(String[] args) {
//        System.out.println(maxProfit(4 , new int[]{1,2,4,2,5,7,2,4,9,0,9}));
    }

    public int maxProfit(int k, int[] prices) {
        if(k==0) return 0;
        if (k > prices.length / 2) {
            return maxProfitNormal(prices);
        }
        //第i次交易后持有/不持有的金额
        int[][] states = new int[k][2];//0：买入，1：卖出
        for (int i = 0; i < k; i++) {
            states[i][0] = -prices[0];
        }
        for (int price : prices) {
            for (int i = 0; i < k; i++) {
                states[i][0] = Math.max(states[i][0], (i>0?states[i - 1][1]:0) - price);
                states[i][1] = Math.max(states[i][1], (i>0?states[i][0]:states[0][0]) + price);
            }
        }
        return states[k-1][1];
    }

    private int maxProfitNormal(int[] prices) {
        int res = 0;
        int n = prices.length;
        for (int i = 0; i < n - 1; i++) {
            //1234，的局部最优是2-1=1，3-2=1，4-3=1，整体最优为 4-1 = 1+1+1 = 3
            if (prices[i] < prices[i + 1]) {//遇到升值，直接进行单次买卖：12341215：在2、3、4、2、5卖出，局部最优
                res = res + prices[i + 1] - prices[i];
            }
        }
        return res;
    }



    public int maxProfit2(int k, int[] prices) {
        if(k==0) return 0;
        if(prices.length<2) return 0;
        //第i次交易后持有/不持有的金额
        int[][] states = new int[k][2];//0：买入，1：卖出
        for (int i = 0; i < k; i++) {
            states[i][0] = -prices[0];
        }
        for (int price : prices) {
            for (int i = 0; i < k; i++) {
                states[i][0] = Math.max(states[i][0], (i>0?states[i - 1][1]:0) - price);
                states[i][1] = Math.max(states[i][1], (i>0?states[i][0]:states[0][0]) + price);
            }
        }
        return states[k-1][1];
    }
}
